//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例： 
//
// 输入：n = 3
//输出：[
//       "((()))",
//       "(()())",
//       "(())()",
//       "()(())",
//       "()()()"
//     ]
// 
// Related Topics 字符串 回溯算法 
// 👍 1489 👎 0

package com.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：括号生成
class P22GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new P22GenerateParentheses().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> list = new ArrayList<>();

            backtrack(list, new StringBuilder(), 0, 0, n);
            return list;
        }

        /**
         * @param list
         * @param stringBuilder
         * @param numOpen       “(”的数量
         * @param numClose      “)”的数量
         * @param n
         */
        private void backtrack(List<String> list, StringBuilder stringBuilder, int numOpen, int numClose, int n) {
            if (stringBuilder.length() == 2 * n) {
                list.add(stringBuilder.toString());
                return;
            }
            if (numOpen < n) {
                stringBuilder.append("(");
                backtrack(list, stringBuilder, numOpen + 1, numClose, n);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
            if (numClose < numOpen) {
                stringBuilder.append(")");
                backtrack(list, stringBuilder, numOpen, numClose + 1, n);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}